A communication network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting communications (e.g., data, voice, video) between communication units (end nodes), such as personal computers, certain telephones, personal digital assistants (PDAs), video units and the like. Many types of communication networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect nodes over dedicated private communications links located in the same general geographical location, such as a building or campus. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol is a set of rules defining how the nodes interact with each other.
A data cache is a collection of data which duplicates original values that are typically stored elsewhere on a computer system or in a communication network where the original data are expensive, usually in terms of access time, to fetch or compute relative to fetching the data from the data cache. Once data is stored in a data cache, future use can be made by accessing the cache copy rather than re-fetching or re-computing the original data so that the average access time associated with accessing the data is lower. Data caches have proven extremely effective in areas of computing where access patterns to data in typical computer applications mean that the same data are often used several times or that data near to each other are accessed close together in time.
A data cache typically comprises a pool of entries wherein each entry holds data which is a copy of original data that is usually stored in a backing store. When a cache client wishes to access the data, presumably in the backing store, a check is performed to determine if the data resides in the cache. If the data is found in the cache, the cache copy of the data is returned to the client instead of the backing store version of the data. This situation is commonly referred to as a “cache hit” situation, meaning that the client “hit” on the data in the data cache (and consequently did not have to fetch the data from the backing store).
Alternatively, a “cache miss” is a situation where the data cache is consulted and found not to contain the data. In this situation, the data is typically fetched from the backing store and presented to the client. In addition, a copy of the data may be placed in the data cache to avoid incurring a cache miss the next time the data is accessed.
Data caches typically have limited storage, thus, in some situations data that is moved from the backing store to the cache will displace other data already in the cache. The data that is displaced is often selected on the basis of a replacement policy. One commonly used replacement policy is the well-known “least recently used” (LRU) policy. In accordance with the LRU policy, when old data in the cache needs to be displaced to make way for new data, the least recently used data in the cache is the data that is displaced.
When data is written to the data cache, at some point in time it is eventually written to the backing store as well. Writing data to the backing store is typically controlled by what is often referred to as a “write policy.” Two well-known write policies that are often employed by data cache systems include the “write-through” policy and the “write-back” policy.
The write-through policy typically involves writing the data to the backing store at the time that the data is being written to the data cache. Thus, in a data cache that employs a write-through policy, the data contained in the data cache is said to be consistent (in agreement) with the data contained in the backing store. The write-back policy typically involves writing the data to the backing store when the data is being displaced by other data based on the data cache's replacement policy. Here, the data in the data cache and the backing store may be “inconsistent,” that is, not in agreement.
Some communication networks employ distributed caches where a node in the network (usually called a central node) maintains a master copy of the cache which is distributed to other nodes in the network (usually called distributed nodes) for their use. In such arrangements, it is important that the data in the master copy be in synchronization with the copies maintained at the distributed nodes. Moreover, it may be important that the data caches be kept in synchronization in a near real time manner thus warranting that the data caches be quickly re-synchronized after problems caused by, e.g., intermittent connections between the central node and the distributed nodes.
One technique that may be used to synchronize data caches in a distributed caching system involves a bulk transfer of data contained in the central node's data cache to each of the distributed nodes. Here, the content of the central node's data cache is transferred “in bulk” to each distributed node which copies the contents to its data cache, overwriting its data cache's previous contents.
Another technique that may be used to synchronize data caches in a distributed caching system involves the use of revision numbers which reflect a version of data contained in the data caches. Here, each data cache may comprise one or more records configured to hold data in the cache. Each record is associated with a key which represents the data in the record and a revision number which represents a version of the data in the record. Each time the content of a particular record changes (e.g., data in the record is added, modified or deleted), its revision number is updated. To synchronize the content of the central node's data cache with a distributed node's data cache, the distributed node transfers the revision numbers and keys for all its data cache records to the central node. The central node uses this information to identify records that are out of date on the distributed node. The central node then transfers an updated copy of the identified out of date records to the distributed node.
Yet another technique that may be used to synchronize data caches in a distributed caching system involves the use of messages which are used by a central node to update data in caches located in the distributed nodes. Here, when information contained in a record changes in the central node's data cache, the change is propagated to the distributed nodes using messages which are acknowledged by the distributed nodes. If a distributed node has not acknowledged a change after some predetermined period of time, the central server may resend the change to the distributed node. The central node may maintain lists to track which distributed nodes have which changes.